{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Number of Ways to Split a String"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #math #string"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数学 #字符串"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: numWays"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #分割字符串的方案数"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个二进制串&nbsp;<code>s</code>&nbsp; （一个只包含 0 和 1 的字符串），我们可以将 <code>s</code>&nbsp;分割成 3 个 <strong>非空</strong>&nbsp;字符串 s1, s2, s3 （s1 + s2 + s3 = s）。</p>\n",
    "\n",
    "<p>请你返回分割&nbsp;<code>s</code>&nbsp;的方案数，满足 s1，s2 和 s3 中字符 &#39;1&#39; 的数目相同。</p>\n",
    "\n",
    "<p>由于答案可能很大，请将它对 10^9 + 7 取余后返回。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>s = &quot;10101&quot;\n",
    "<strong>输出：</strong>4\n",
    "<strong>解释：</strong>总共有 4 种方法将 s 分割成含有 &#39;1&#39; 数目相同的三个子字符串。\n",
    "&quot;1|010|1&quot;\n",
    "&quot;1|01|01&quot;\n",
    "&quot;10|10|1&quot;\n",
    "&quot;10|1|01&quot;\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>s = &quot;1001&quot;\n",
    "<strong>输出：</strong>0\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>s = &quot;0000&quot;\n",
    "<strong>输出：</strong>3\n",
    "<strong>解释：</strong>总共有 3 种分割 s 的方法。\n",
    "&quot;0|0|00&quot;\n",
    "&quot;0|00|0&quot;\n",
    "&quot;00|0|0&quot;\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 4：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>s = &quot;100100010100110&quot;\n",
    "<strong>输出：</strong>12\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>s[i] == &#39;0&#39;</code>&nbsp;或者&nbsp;<code>s[i] == &#39;1&#39;</code></li>\n",
    "\t<li><code>3 &lt;= s.length &lt;= 10^5</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [number-of-ways-to-split-a-string](https://leetcode.cn/problems/number-of-ways-to-split-a-string/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [number-of-ways-to-split-a-string](https://leetcode.cn/problems/number-of-ways-to-split-a-string/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['\"10101\"', '\"1001\"', '\"0000\"']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOD = 10**9 + 7\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, words: List[str], target: str) -> int:\n",
    "        n = len(target)\n",
    "        m, l = len(words), len(words[0])\n",
    "\n",
    "        if l < n:\n",
    "            return 0\n",
    "        \n",
    "        freq = [[0] * 26 for _ in range(l)]\n",
    "\n",
    "        def str_idx(x:str):\n",
    "            return ord(x) - ord('a')\n",
    "\n",
    "        for i in range(l):\n",
    "            for j in range(m):\n",
    "                ch = str_idx(words[j][i])\n",
    "                freq[i][ch] += 1\n",
    "\n",
    "        f = [0] * (n + 1)\n",
    "        f[0] = 1\n",
    "        # f[0] = freq[0][str_idx(target[0])]\n",
    "\n",
    "        for i in range(0, l):\n",
    "            for j in range(n, 0, -1):\n",
    "                f[j] += f[j-1] * freq[i][str_idx(target[j-1])]\n",
    "                f[j] %= MOD\n",
    "\n",
    "        return f[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, words: List[str], target: str) -> int:\n",
    "        mod = 10**9 + 7\n",
    "        \n",
    "        def dfs(dp, cnt, target, i, j, n, m):\n",
    "            if j == m:\n",
    "                return 1\n",
    "            if n - i < m - j:\n",
    "                return 0\n",
    "            if dp[i][j] != -1:\n",
    "                return dp[i][j]\n",
    "            \n",
    "            val = cnt[i][ord(target[j]) - ord('a')] * dfs(dp, cnt, target, i + 1, j + 1, n, m)\n",
    "            val += dfs(dp, cnt, target, i + 1, j, n, m)\n",
    "            val %= mod\n",
    "            dp[i][j] = val\n",
    "            return val\n",
    "        \n",
    "        n = len(words[0])\n",
    "        cnt = [[0] * 26 for _ in range(n)]\n",
    "        for s in words:\n",
    "            for i in range(n):\n",
    "                cnt[i][ord(s[i]) - ord('a')] += 1\n",
    "        \n",
    "        m = len(target)\n",
    "        dp = [[-1] * m for _ in range(n)]\n",
    "        return dfs(dp, cnt, target, 0, 0, n, m)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import Counter\n",
    "\n",
    "_MOD = 10 ** 9 + 7\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, words: List[str], target: str) -> int:\n",
    "        l_w, l_t = len(words[0]), len(target)\n",
    "        if l_t > l_w:\n",
    "            return 0\n",
    "        cnts = [Counter([w[i] for w in words]) for i in range(l_w)]\n",
    "        f = [[1 for _ in range(l_w)]]\n",
    "        for i in range(1, l_t + 1):\n",
    "            f.append([(f[i - 1][0] * cnts[i - 1][target[i - 1]]) % _MOD])\n",
    "            for j in range(1, l_w - i + 1):\n",
    "                f[i].append((f[i - 1][j] * cnts[i + j - 1][target[i - 1]] + f[i][j - 1]) % _MOD)\n",
    "        return f[l_t][l_w - l_t]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, words: List[str], target: str) -> int:\n",
    "\n",
    "        MOD = 10**9 + 7\n",
    "        m, n = len(words), len(target)\n",
    "        l = len(words[0])\n",
    "\n",
    "        # Count of each character in each position of words\n",
    "        counts = [[0] * 26 for _ in range(l)]\n",
    "        for word in words:\n",
    "            for i, c in enumerate(word):\n",
    "                counts[i][ord(c) - ord('a')] += 1\n",
    "\n",
    "        # DP array initialization\n",
    "        dp = [[0] * l for _ in range(n)]\n",
    "        dp[0][0] = counts[0][ord(target[0]) - ord('a')]\n",
    "\n",
    "        # DP transition\n",
    "        for j in range(1, l):\n",
    "            dp[0][j] = dp[0][j - 1] + counts[j][ord(target[0]) - ord('a')]\n",
    "\n",
    "        for i in range(1, n):\n",
    "            for j in range(i, l):\n",
    "                dp[i][j] = dp[i][j - 1] + dp[i - 1][j - 1] * counts[j][ord(target[i]) - ord('a')]\n",
    "                dp[i][j] %= MOD\n",
    "\n",
    "        return dp[n - 1][l - 1]\n",
    "\n",
    "\n",
    "        # 题目意思：words里面选取的顺序并不重要，但是我们选取的第几个字母是需要单调递增的一个特点\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, words: List[str], target: str) -> int:\n",
    "        mod = 10**9 + 7\n",
    "        \n",
    "        # 计算字符在每个位置的频率\n",
    "        freq = [[0] * 26 for _ in range(len(words[0]))]\n",
    "        for word in words:\n",
    "            for j, char in enumerate(word):\n",
    "                freq[j][ord(char) - ord('a')] += 1\n",
    "\n",
    "        # 初始化动态规划数组\n",
    "        m, n = len(target), len(words[0])\n",
    "        dp = [[0] * (n + 1) for _ in range(m + 1)]\n",
    "        for j in range(n + 1):\n",
    "            dp[0][j] = 1\n",
    "\n",
    "        # 动态规划计算\n",
    "        for i in range(1, m + 1):\n",
    "            for j in range(1, n + 1):\n",
    "                dp[i][j] = dp[i][j - 1] + dp[i - 1][j - 1] * freq[j - 1][ord(target[i - 1]) - ord('a')]\n",
    "                dp[i][j] %= mod\n",
    "\n",
    "        return dp[m][n]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, words: List[str], target: str) -> int:\n",
    "\n",
    "        MOD = 10**9 + 7\n",
    "        m, n = len(words), len(target)\n",
    "        l = len(words[0])\n",
    "\n",
    "        # Count of each character in each position of words\n",
    "        counts = [[0] * 26 for _ in range(l)]\n",
    "        for word in words:\n",
    "            for i, c in enumerate(word):\n",
    "                counts[i][ord(c) - ord('a')] += 1\n",
    "\n",
    "        # DP array initialization\n",
    "        dp = [[0] * l for _ in range(n)]\n",
    "        dp[0][0] = counts[0][ord(target[0]) - ord('a')]\n",
    "\n",
    "        # DP transition\n",
    "        for j in range(1, l):\n",
    "            dp[0][j] = dp[0][j - 1] + counts[j][ord(target[0]) - ord('a')]\n",
    "\n",
    "        for i in range(1, n):\n",
    "            for j in range(i, l):\n",
    "                dp[i][j] = dp[i][j - 1] + dp[i - 1][j - 1] * counts[j][ord(target[i]) - ord('a')]\n",
    "                dp[i][j] %= MOD\n",
    "\n",
    "        return dp[n - 1][l - 1]\n",
    "\n",
    "        # # Test cases\n",
    "        # words1 = [\"acca\",\"bbbb\",\"caca\"]\n",
    "        # target1 = \"aba\"\n",
    "        # print(numWays(words1, target\n",
    "\n",
    "\n",
    "        # 题目意思：words里面选取的顺序并不重要，但是我们选取的第几个字母是需要单调递增的一个特点\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, words: List[str], target: str) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "        n = len(target)\n",
    "        m = len(words[0])\n",
    "        if n > m:\n",
    "            return 0\n",
    "        #记录idx位上字母出现次数\n",
    "        freq = [[0] * 26 for _ in range(m)]\n",
    "        for word in words:\n",
    "            for i in range(len(word)):\n",
    "                idx = ord(word[i]) - ord('a')\n",
    "                freq[i][idx] += 1\n",
    "        #dp[i][j] target中前j个字符与字典中前i个字匹配的方案数\n",
    "        dp = [[0] * m for _ in range(n)]\n",
    "        dp[0][0] = freq[0][ord(target[0]) - ord('a')]\n",
    "        for j in range(1,m):\n",
    "            dp[0][j] += dp[0][j - 1] + freq[j][ord(target[0]) - ord('a')]\n",
    "        for i in range(1,n):\n",
    "            idx = ord(target[i]) - ord('a')\n",
    "            for j in range(i,m):\n",
    "                dp[i][j] = (dp[i - 1][j - 1] * freq[j][idx] + dp[i][j - 1]) % MOD\n",
    "        return dp[n -1][m - 1]\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, words: List[str], target: str) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "        n = len(target)\n",
    "        m = len(words[0])\n",
    "        if n > m:\n",
    "            return 0\n",
    "\n",
    "        #记录idx位上字母出现次数\n",
    "        freq = [[0] * 26 for _ in range(m)]\n",
    "        for word in words:\n",
    "            for i in range(m):\n",
    "                idx = ord(word[i]) - ord('a')\n",
    "                freq[i][idx] += 1\n",
    "        \n",
    "        #dp[i][j] 字典中前j个字符与target中前i个字匹配的方案数\n",
    "        dp = [[0] * (m + 1) for _ in range(n + 1)]\n",
    "        dp[0][0] = 1\n",
    "        for i in range(1,n + 1):\n",
    "            idx = ord(target[i - 1]) - ord('a')\n",
    "            for j in range(i,m + 1):\n",
    "                dp[0][j] = 1\n",
    "                dp[i][j] = (dp[i - 1][j - 1] * freq[j - 1][idx] + dp[i][j - 1]) % MOD\n",
    "        return dp[n][m]\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, words: List[str], target: str) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "        n = len(target)\n",
    "        m = len(words[0])\n",
    "        if n > m:\n",
    "            return 0\n",
    "\n",
    "        #记录idx位上字母出现次数\n",
    "        freq = [[0] * 26 for _ in range(m)]\n",
    "        for word in words:\n",
    "            for i in range(m):\n",
    "                idx = ord(word[i]) - ord('a')\n",
    "                freq[i][idx] += 1\n",
    "        \n",
    "        #dp[i][j] target中前j个字符与字典中前i个字匹配的方案数\n",
    "        dp = [[0] * (m + 1) for _ in range(n + 1)]\n",
    "        dp[0][0] = 1\n",
    "        for i in range(1,n + 1):\n",
    "            idx = ord(target[i - 1]) - ord('a')\n",
    "            for j in range(1,m + 1):\n",
    "                dp[0][j] = 1\n",
    "                dp[i][j] = (dp[i - 1][j - 1] * freq[j - 1][idx] + dp[i][j - 1]) % MOD\n",
    "        return dp[n][m]\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import Counter\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, words: List[str], target: str) -> int:\n",
    "        MOD = 10**9+7\n",
    "        n,m = len(words),len(words[0])\n",
    "        t = len(target)\n",
    "        if m<t: return 0\n",
    "        cot = [Counter([e[i] for e in words]) for i in range(m)]\n",
    "        # dp[i][j]表示用words[i:]组成target[j:]的方案数\n",
    "        dp = [[0]*t for _ in range(m)]\n",
    "        dp[m-1][t-1] = 0 if target[-1] not in cot[m-1] else cot[m-1][target[-1]]\n",
    "        for i in range(m-2, -1, -1):\n",
    "            dp[i][t-1] = cot[i][target[t-1]] + dp[i+1][t-1]\n",
    "        for i in range(m-2, -1, -1):\n",
    "            for j in range(t-2, -1, -1):\n",
    "                dp[i][j] = dp[i+1][j] + cot[i][target[j]]*dp[i+1][j+1]\n",
    "                dp[i][j]%=MOD\n",
    "        return dp[0][0]%MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, words: List[str], target: str) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "        n, m = len(target), len(words[0])\n",
    "        count = [[0] * 26 for _ in range(m)]  # count[i][j] 统计每个单词第i个字母的ord是j的数目\n",
    "        for i in range(m):\n",
    "            for w in words:\n",
    "                count[i][ord(w[i]) - ord('a')] += 1\n",
    "        dp = [[0] * m for _ in range(n)]  # dp[i][j] 表示由每个单词的前j个字母，组成target的前i个字母的所有可能\n",
    "        dp[0][0] = sum(1 for w in words if w[0] == target[0])\n",
    "        for i in range(n):\n",
    "            for j in range(i, m):  # i <= j\n",
    "                if j == 0 == i: continue\n",
    "                if i == 0:\n",
    "                    dp[i][j] = dp[i][j - 1] + count[j][ord(target[0]) - ord('a')]\n",
    "                else:\n",
    "                    dp[i][j] = dp[i][j - 1] + dp[i - 1][j - 1] * count[j][ord(target[i]) - ord('a')]\n",
    "                dp[i][j] %= MOD\n",
    "\n",
    "        # print(dp)\n",
    "        return dp[-1][-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, words: List[str], target: str) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "        n = len(target)\n",
    "        m = len(words[0])\n",
    "        if n > m:\n",
    "            return 0\n",
    "\n",
    "        #记录idx位上字母出现次数\n",
    "        freq = [[0] * 26 for _ in range(m)]\n",
    "        for word in words:\n",
    "            for i in range(m):\n",
    "                idx = ord(word[i]) - ord('a')\n",
    "                freq[i][idx] += 1\n",
    "        \n",
    "        #dp[i][j] 字典中前j个字符与target中前i个字匹配的方案数\n",
    "        dp = [[0] * (m + 1) for _ in range(n + 1)]\n",
    "        dp[0][0] = 1\n",
    "        for i in range(1,n + 1):\n",
    "            idx = ord(target[i - 1]) - ord('a')\n",
    "            for j in range(i,m + 1):\n",
    "                dp[0][j] = 1\n",
    "                dp[i][j] = (dp[i - 1][j - 1] * freq[j - 1][idx] + dp[i][j - 1]) % MOD\n",
    "        return dp[n][m]\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, words: List[str], target: str) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "        n = len(target)\n",
    "        m = len(words[0])\n",
    "        if n > m:\n",
    "            return 0\n",
    "\n",
    "        #记录idx位上字母出现次数\n",
    "        freq = [[0] * 26 for _ in range(m)]\n",
    "        for word in words:\n",
    "            for i in range(m):\n",
    "                idx = ord(word[i]) - ord('a')\n",
    "                freq[i][idx] += 1\n",
    "        \n",
    "        #dp[i][j] target中前j个字符与字典中前i个字匹配的方案数\n",
    "        dp = [[0] * (m + 1) for _ in range(n + 1)]\n",
    "        dp[0][0] = 1\n",
    "        for i in range(1,n + 1):\n",
    "            dp[0][i] = 1\n",
    "            idx = ord(target[i - 1]) - ord('a')\n",
    "            for j in range(1,m + 1):\n",
    "                dp[0][j] = 1\n",
    "                dp[i][j] = (dp[i - 1][j - 1] * freq[j - 1][idx] + dp[i][j - 1]) % MOD\n",
    "        return dp[n][m]\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import *\n",
    "from math import *\n",
    "from functools import cache\n",
    "from queue import *\n",
    "from heapq import *\n",
    "from itertools import *\n",
    "from bisect import bisect_left\n",
    "# start-----------------------------------------------------\n",
    "class Solution:\n",
    "    def numWays(self, words: List[str], target: str) -> int:\n",
    "        mod = int(1e9+7)\n",
    "        m,n = len(words),len(words[0])\n",
    "        k = len(target)\n",
    "        ct = [Counter() for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                ct[i][words[j][i]] += 1\n",
    "        @cache\n",
    "        def f(x, p):\n",
    "            if n - x < k - p:\n",
    "                return 0\n",
    "            if p == k:\n",
    "                return 1\n",
    "            r = 0\n",
    "            if target[p] in ct[x]:\n",
    "                r = (r + ct[x][target[p]] * f(x+1, p+1)) % mod\n",
    "            r = (r + f(x+1, p)) % mod\n",
    "\n",
    "            return r\n",
    "        ans = f(0, 0)\n",
    "        f.cache_clear()\n",
    "        return ans\n",
    "                \n",
    "# end-------------------------------------------------------\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import *\n",
    "from math import *\n",
    "from functools import cache\n",
    "from queue import *\n",
    "from heapq import *\n",
    "from itertools import *\n",
    "from bisect import bisect_left\n",
    "# start-----------------------------------------------------\n",
    "class Solution:\n",
    "    def numWays(self, words: List[str], target: str) -> int:\n",
    "        mod = int(1e9+7)\n",
    "        m,n = len(words),len(words[0])\n",
    "        k = len(target)\n",
    "        ct = [Counter() for _ in range(n)]\n",
    "        # ct[i] 表示第i列的字母以及对应的个数\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                ct[i][words[j][i]] += 1\n",
    "        @cache\n",
    "        def f(x, p):\n",
    "            if n - x < k - p:\n",
    "                return 0\n",
    "            if p == k:\n",
    "                return 1\n",
    "            r = 0\n",
    "            # 可以选择第x列作为target[p]\n",
    "            if target[p] in ct[x]:\n",
    "                r = (r + ct[x][target[p]] * f(x+1, p+1)) % mod\n",
    "            # 不选择第x列作为target[p]\n",
    "            r = (r + f(x+1, p)) % mod\n",
    "            return r\n",
    "        ans = f(0, 0)\n",
    "        f.cache_clear()\n",
    "        return ans\n",
    "                \n",
    "# end-------------------------------------------------------\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# []\n",
    "# [0 => a, b, c]\n",
    "# [1 => c, b, a]\n",
    "# [2 => c, b]\n",
    "# [3 => a, b]\n",
    "# dp[i][j] = dp[i-1][j-1] * pre[i][target[j]] + dp[i-1][j]\n",
    "class Solution:\n",
    "    def numWays(self, words: List[str], target: str) -> int:\n",
    "        words_length = len(words[0])\n",
    "        target_length = len(target)\n",
    "        graph = [collections.defaultdict(int) for _ in range(words_length)]\n",
    "        for word in words:\n",
    "            for idx in range(words_length):\n",
    "                graph[idx][word[idx]] += 1\n",
    "        \n",
    "        dp = [[0] * target_length for _ in range(words_length)]\n",
    "        dp[0][0] = graph[0][target[0]]\n",
    "        for i in range(1, words_length):\n",
    "            dp[i][0] = graph[i][target[0]] + dp[i-1][0]\n",
    "            for j in range(1, min(i+1, target_length)):\n",
    "                dp[i][j] = dp[i-1][j-1] * graph[i][target[j]] + dp[i-1][j]\n",
    "                dp[i][j] %= 10**9 + 7\n",
    "        return dp[-1][-1]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, words: List[str], target: str) -> int:\n",
    "        dct = defaultdict(lambda: defaultdict(int))\n",
    "        n = len(words[0])\n",
    "        for word in words:\n",
    "            for i, w in enumerate(word):\n",
    "                dct[w][i] += 1\n",
    "\n",
    "        m = len(target)\n",
    "        dp = [[0]*(n+1) for _ in range(m+1)]\n",
    "        dp[0][0] = 1\n",
    "        mod = 10**9 + 7\n",
    "        for i in range(m):\n",
    "            dp[i+1][0] = 0\n",
    "            pre = dp[i][0]\n",
    "            for j in range(n):\n",
    "                c = dct[target[i]][j]\n",
    "                dp[i+1][j+1] = (pre*c) % mod\n",
    "                pre += dp[i][j+1]\n",
    "        return sum(dp[-1]) % mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, words: List[str], target: str) -> int:\n",
    "        from collections import defaultdict\n",
    "        m = len(words[0])\n",
    "        n = len(target)\n",
    "        \n",
    "        if n > m:\n",
    "            return 0\n",
    "\n",
    "        chars = [defaultdict(int) for _ in range(m)]\n",
    "        for w in words:\n",
    "            for i in range(m):\n",
    "                chars[i][w[i]] += 1\n",
    "        \n",
    "        dp = [[0]*n for _ in range(m)]\n",
    "        dp[0][0] = chars[0][target[0]]\n",
    "        for j in range(1,m):\n",
    "            dp[j][0] = dp[j-1][0] + chars[j][target[0]]\n",
    "\n",
    "        for i in range(1,n):\n",
    "            for j in range(i,m):\n",
    "                dp[j][i] = dp[j-1][i] + dp[j-1][i-1]*chars[j][target[i]]\n",
    "                dp[j][i] %= (10**9+7)\n",
    "        \n",
    "        return dp[-1][-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, words: List[str], target: str) -> int:\n",
    "        MOD = int(1e9 + 7)\n",
    "        m = len(words[0])\n",
    "        cnt = [Counter(row) for row in zip(*words)]\n",
    "        \n",
    "        @cache\n",
    "        def dfs(i,k):\n",
    "            if i == len(target):\n",
    "                return 1\n",
    "            ans = 0\n",
    "            for j in range(k,m):\n",
    "                if m - j < len(target) - i:\n",
    "                    break\n",
    "                if target[i] in cnt[j]:\n",
    "                    ans += cnt[j][target[i]] * dfs(i + 1,j + 1) % MOD\n",
    "                    ans %= MOD\n",
    "            return ans\n",
    "        \n",
    "        return dfs(0,0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, words: List[str], target: str) -> int:\n",
    "        MOD = int(1e9 + 7)\n",
    "        m = len(words[0])\n",
    "        cnt = [Counter(w[i] for w in words) for i in range(m)]\n",
    "        \n",
    "        @cache\n",
    "        def dfs(i,k):\n",
    "            if i == len(target):\n",
    "                return 1\n",
    "            ans = 0\n",
    "            for j in range(k,m):\n",
    "                if m - j < len(target) - i:\n",
    "                    break\n",
    "                if target[i] in cnt[j]:\n",
    "                    ans += cnt[j][target[i]] * dfs(i + 1,j + 1) % MOD\n",
    "                    ans %= MOD\n",
    "            return ans\n",
    "        \n",
    "        return dfs(0,0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, words: List[str], target: str) -> int:\n",
    "        MOD = int(1e9 + 7)\n",
    "        m = len(words[0])\n",
    "        cnt = [Counter(row) for row in zip(*words)]\n",
    "        n = len(target)\n",
    "\n",
    "        @cache\n",
    "        def dfs(i,k):\n",
    "            if i == n:\n",
    "                return 1\n",
    "            if m - k < n - i:\n",
    "                return 0\n",
    "            ans = dfs(i,k + 1)\n",
    "            if target[i] in cnt[k]:\n",
    "                ans += cnt[k][target[i]] * dfs(i + 1,k + 1) % MOD\n",
    "                ans %= MOD\n",
    "            return ans\n",
    "        \n",
    "        return dfs(0,0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOD = 10 ** 9 + 7\n",
    "class Solution:\n",
    "    def numWays(self, words: List[str], target: str) -> int:\n",
    "        m, n = len(words),len(words[0])\n",
    "        l = len(target)\n",
    "        g = [Counter() for _ in range(n)]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                g[j][words[i][j]] += 1\n",
    "        @cache\n",
    "        def dfs(i,j):\n",
    "            if j == l:  return 1\n",
    "            elif n - i < l - j: return 0\n",
    "            if not g[i][target[j]]: return dfs(i + 1, j)\n",
    "            return (dfs(i + 1, j) + g[i][target[j]] * dfs(i + 1, j + 1)) % MOD\n",
    "        return dfs(0,0)\n",
    "\n",
    "            \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, words: List[str], target: str) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "        m = len(words)\n",
    "        n = len(words[0])\n",
    "        Count = defaultdict(int)\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                Count[(i, words[j][i])] += 1\n",
    "        l = len(target)\n",
    "        dp = [[0]*l for _ in range(n) ]\n",
    "        dp[0][0] = Count[(0, target[0])]\n",
    "        for i in range(1,n):\n",
    "            dp[i][0] =dp[i-1][0]+ Count[(i, target[0])]%MOD #dp[i-1][j-1],j-1需要大于0\n",
    "            for j in range(1,l):\n",
    "                dp[i][j] = dp[i-1][j] #先加上dp[i-1][j]的匹配完结果数\n",
    "                if (i, target[j]) in Count.keys():#如果当前target[j]在i列中\n",
    "                    dp[i][j] += dp[i-1][j-1]*Count[(i, target[j])]%MOD\n",
    "        # print(dp)\n",
    "        return dp[-1][-1]%MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, words: List[str], target: str) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "        m = len(words)\n",
    "        n = len(words[0])\n",
    "        Count = defaultdict(int)\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                Count[(i, words[j][i])] += 1\n",
    "        l = len(target)\n",
    "        dp = [[0]*l for _ in range(n) ]\n",
    "        dp[0][0] = Count[(0, target[0])]\n",
    "        print(dp)\n",
    "        for i in range(1,n):\n",
    "            dp[i][0] =dp[i-1][0]+ Count[(i, target[0])]%MOD\n",
    "            for j in range(1,l):\n",
    "                dp[i][j] = dp[i-1][j] #先加上dp[i-1][j]\n",
    "                if (i, target[j]) in Count.keys():#如果当前target[j]在i列中\n",
    "                    dp[i][j] += dp[i-1][j-1]*Count[(i, target[j])]%MOD\n",
    "        # print(dp)\n",
    "        return dp[-1][-1]%MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, words: List[str], target: str) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "        m = len(words)\n",
    "        n = len(words[0])\n",
    "        Count = defaultdict(int)\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                Count[(i, words[j][i])] += 1\n",
    "        l = len(target)\n",
    "        dp = [[0]*l for _ in range(n) ]\n",
    "        dp[0][0] = Count[(0, target[0])]\n",
    "        print(dp)\n",
    "        for i in range(1,n):\n",
    "            dp[i][0] =dp[i-1][0]+ Count[(i, target[0])]%MOD\n",
    "            for j in range(1,l):\n",
    "                dp[i][j] = dp[i-1][j] #先加上dp[i-1][j]\n",
    "                if (i, target[j]) in Count.keys():#如果当前target[j]在i列中\n",
    "                    dp[i][j] += dp[i-1][j-1]*Count[(i, target[j])]%MOD\n",
    "        # print(dp)\n",
    "        return dp[-1][-1]%MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, words: List[str], target: str) -> int:\n",
    "        m, n = len(words), len(words[0])\n",
    "        l = len(target)\n",
    "        d = [{} for i in range(n)]#哈希表数组\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                c = words[i][j]\n",
    "                d[j][c] = d[j].get(c, 0) + 1\n",
    "        @lru_cache(None)\n",
    "        def dfs(i, j):#words字符下标，target字符下标\n",
    "            if j == l:#target遍历完，可行\n",
    "                return 1\n",
    "            elif n - i < l - j:#words中的剩余字符数量小于target的剩余字符数量，方案不可行\n",
    "                return 0\n",
    "            if target[j] not in d[i]:#如果不存在哈希表中\n",
    "                return dfs(i + 1, j)\n",
    "            return (dfs(i + 1, j) + d[i][target[j]] * dfs(i + 1, j + 1)) % mod\n",
    "        mod = 10 ** 9 + 7\n",
    "        return dfs(0, 0)\n",
    "\n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, words: List[str], target: str) -> int:\n",
    "       MOD = 10 ** 9 + 7\n",
    "       @cache\n",
    "       def dfs(i: int, j: int) -> int:\n",
    "          if i == len(target):\n",
    "             return 1\n",
    "          if j == n:\n",
    "             return 0\n",
    "          if len(target) - i > n - j:\n",
    "             return 0\n",
    "          return (dfs(i, j + 1) + cnts[j][ord(target[i]) - ord('a')] * dfs(i + 1, j + 1)) % MOD\n",
    "       n = len(words[0])\n",
    "       cnts = [[0] * 26 for _ in range(n)]\n",
    "       for w in words:\n",
    "          for i, c in enumerate(w):\n",
    "             cnts[i][ord(c) - ord('a')] += 1\n",
    "       return dfs(0, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, words: List[str], target: str) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "        n = len(target)\n",
    "        m = len(words)\n",
    "        p = len(words[0])\n",
    "\n",
    "        cnt = [[0] * 26 for _ in range(p)]\n",
    "        for i in range(m):\n",
    "            for j in range(p):\n",
    "                cnt[j][ord(words[i][j]) - ord('a')] += 1\n",
    "        \n",
    "        @cache\n",
    "        def compute(i,j):\n",
    "            if j == n:\n",
    "                return 1\n",
    "            if p - i < n - j:\n",
    "                return 0\n",
    "            \n",
    "            return (compute(i+1,j) + compute(i+1,j+1)*cnt[i][ord(target[j])-ord('a')])%MOD\n",
    "\n",
    "        return compute(0,0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOD = 10**9 + 7\n",
    "class Solution:\n",
    "    def numWays(self, words: List[str], target: str) -> int:\n",
    "        n, m = len(target), len(words[0])\n",
    "        rec = [[0] * 26 for _ in range(m)]\n",
    "        for w in words:\n",
    "            for i in range(m):\n",
    "                rec[i][ord(w[i]) - ord('a')] += 1\n",
    "        \n",
    "        @cache\n",
    "        def dfs(i, j):\n",
    "            if i < 0:\n",
    "                return 1\n",
    "            res = 0\n",
    "            for k in range(i, j + 1):\n",
    "                if rec[k][ord(target[i]) - ord('a')]:\n",
    "                    res += rec[k][ord(target[i]) - ord('a')] * dfs(i - 1, k - 1)\n",
    "                    res %= MOD\n",
    "            return res\n",
    "        return dfs(n - 1, m - 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, words: List[str], target: str) -> int:\n",
    "        n = len(words[0])\n",
    "        MOD = 10 ** 9 + 7\n",
    "        d = [[0] * 26 for _ in range(n)]\n",
    "        for i in words:\n",
    "            for j,c in enumerate(i):\n",
    "                d[j][ord(c) - 97] += 1\n",
    "\n",
    "        @lru_cache(None)\n",
    "        def dp(m,k):\n",
    "            mval = ord(target[m-1]) - 97\n",
    "            if m == 1:\n",
    "                return d[k][mval]\n",
    "            if k+1 < m:\n",
    "                return 0\n",
    "            \n",
    "            c = 0\n",
    "            for i in range(m-2, k):\n",
    "                c = (c + d[k][mval] * dp(m-1,i)) % MOD\n",
    "            # print(m,k,c, mval, d[k][mval])\n",
    "            return c\n",
    "        return sum([dp(len(target), i) for i in range(n)]) % MOD\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, words: List[str], target: str) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "        n = len(target)\n",
    "        m = len(words[0])\n",
    "        if n > m:\n",
    "            return 0\n",
    "        #记录idx位上字母出现次数\n",
    "        freq = [[0] * 26 for _ in range(m)]\n",
    "        for word in words:\n",
    "            for i in range(len(word)):\n",
    "                idx = ord(word[i]) - ord('a')\n",
    "                freq[i][idx] += 1\n",
    "        @cache\n",
    "        def dfs(idx,k) -> int:\n",
    "            if idx == n:\n",
    "                return 1\n",
    "            res = 0\n",
    "            num = ord(target[idx]) - ord('a')\n",
    "            for i in range(k,m):\n",
    "                if freq[i][num]:\n",
    "                    res += freq[i][num] * dfs(idx + 1,i + 1) % MOD\n",
    "                if m - i < n - idx:\n",
    "                    break\n",
    "            return res % MOD\n",
    "        return dfs(0,0)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    @lru_cache\n",
    "    def build(self, i, k):\n",
    "        if self.l-k < self.t-i:\n",
    "            return 0\n",
    "\n",
    "        if i == self.t:\n",
    "            return 1\n",
    "\n",
    "        if i*(self.l+1)+k in self.d:\n",
    "            return self.d[i*(self.l+1)+k]\n",
    "        \n",
    "        r = self.rec[k][ord(self.target[i])-ord(\"a\")]*self.build(i+1, k+1) + self.build(i, k+1)\n",
    "        self.d[i*(self.l+1)+k] = r\n",
    "        return r\n",
    "\n",
    "    def numWays(self, words: List[str], target: str) -> int:\n",
    "        n = len(words)\n",
    "        self.t = t = len(target)\n",
    "        self.target = target\n",
    "        self.l = l = len(words[0])\n",
    "        self.rec = rec = [[0]*26 for _ in range(l)]\n",
    "        for i in range(n):\n",
    "            for j in range(l):\n",
    "                rec[j][ord(words[i][j])-ord(\"a\")] += 1\n",
    "\n",
    "        self.d = {}\n",
    "        return self.build(0, 0) % (10**9+7)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, words: List[str], target: str) -> int:\n",
    "        cts = []\n",
    "        for i in range(len(words[0])):\n",
    "            cts.append(collections.Counter(words[j][i] for j in range(len(words))))\n",
    "            \n",
    "        n = len(cts)\n",
    "                    \n",
    "        @lru_cache(None)\n",
    "        def dfs(cur, t):\n",
    "            if len(t) > n - cur:\n",
    "                return 0\n",
    "                \n",
    "            if not t:\n",
    "                return 1\n",
    "                \n",
    "            return (dfs(cur+1, t) + cts[cur][t[0]] * dfs(cur+1, t[1:])) % (10**9 + 7)\n",
    "        \n",
    "        return dfs(0, target)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, words: List[str], target: str) -> int:\n",
    "        mod = 10 ** 9 + 7\n",
    "        m,n = len(words[0]),len(target)\n",
    "        \n",
    "        # 存储每列上的元素个数\n",
    "        index_count = [Counter(w[i] for w in words) for i in range(len(words[0]))]\n",
    "      \n",
    "        @lru_cache(None)\n",
    "        def dfs(index,k):\n",
    "            if index == n:\n",
    "                return 1\n",
    "            if k == m:\n",
    "                return 0\n",
    "            res = dfs(index,k + 1)\n",
    "            if target[index] in index_count[k]:\n",
    "                res += index_count[k][target[index]] * dfs(index + 1,k + 1) % mod\n",
    "                res %= mod\n",
    "            return res\n",
    "        \n",
    "        return dfs(0,0) % mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, words: List[str], target: str) -> int:\n",
    "        MOD = 10**9 + 7\n",
    "        ans = 0\n",
    "        n = len(words[0])\n",
    "        m = len(target)\n",
    "        pos = [Counter(w[i] for w in words) for i in range(len(words[0]))]\n",
    "\n",
    "        @cache\n",
    "        def dfs(p, w):\n",
    "            if w == len(target): return 1\n",
    "            if p == n: return 0\n",
    "            res = dfs(p + 1, w)\n",
    "            if target[w] in pos[p]: \n",
    "                res = (res + dfs(p + 1, w + 1) * pos[p][target[w]]) % MOD\n",
    "            return res\n",
    "        return dfs(0, 0) % MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWays1(self, words: List[str], target: str) -> int:\n",
    "        n=len(words[0])\n",
    "        m=len(words)\n",
    "        dic_lst=[Counter([words[i][k] for i in range(m)]) for k in range(n)]\n",
    "        t=len(target)\n",
    "        dp=[[0]*t for i in range(n)]\n",
    "        cur=0\n",
    "        for i in range(n):\n",
    "            if target[0] in dic_lst[i]:\n",
    "                cur+=dic_lst[i][target[0]]\n",
    "            dp[i][0]=cur\n",
    "        for i in range(1,n):\n",
    "            for k in range(1,t):\n",
    "                if target[k] in dic_lst[i]:\n",
    "                    dp[i][k]=dic_lst[i][target[k]]*dp[i-1][k-1]+dp[i-1][k]\n",
    "                else:\n",
    "                    dp[i][k]=dp[i-1][k]\n",
    "        return dp[-1][-1]%(10**9+7)\n",
    "\n",
    "    def numWays(self, words: List[str], target: str) -> int:\n",
    "        mod = 10 ** 9 + 7\n",
    "        m,n = len(words[0]),len(target)\n",
    "        \n",
    "        # 存储每列上的元素个数\n",
    "        index_count = [Counter(w[i] for w in words) for i in range(len(words[0]))]\n",
    "      \n",
    "        @lru_cache(None)\n",
    "        def dfs(index,k):\n",
    "            if index == n:\n",
    "                return 1\n",
    "            if k == m:\n",
    "                return 0\n",
    "            res = dfs(index,k + 1)\n",
    "            if target[index] in index_count[k]:\n",
    "                res += index_count[k][target[index]] * dfs(index + 1,k + 1)\n",
    "            return res\n",
    "        \n",
    "        return dfs(0,0) % mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, words: List[str], target: str) -> int:\n",
    "        mod = 10 ** 9 + 7\n",
    "        m,n = len(words[0]),len(target)\n",
    "        \n",
    "        # 存储每列上的元素个数\n",
    "        index_count = [Counter(w[i] for w in words) for i in range(len(words[0]))]\n",
    "      \n",
    "        @lru_cache(None)\n",
    "        def dfs(index,k):\n",
    "            if index == n:\n",
    "                return 1\n",
    "            if k == m:\n",
    "                return 0\n",
    "            res = dfs(index,k + 1)\n",
    "            if target[index] in index_count[k]:\n",
    "                res += index_count[k][target[index]] * dfs(index + 1,k + 1)\n",
    "            return res\n",
    "        \n",
    "        return dfs(0,0) % mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, words: List[str], target: str) -> int:\n",
    "       MOD = 10 ** 9 + 7\n",
    "       @cache\n",
    "       def dfs(i: int, j: int) -> int:\n",
    "          if i == len(target):\n",
    "             return 1\n",
    "          if j == n:\n",
    "             return 0\n",
    "          return (dfs(i, j + 1) + cnts[j][ord(target[i]) - ord('a')] * dfs(i + 1, j + 1)) % MOD\n",
    "       n = len(words[0])\n",
    "       if len(target) > n:\n",
    "          return 0\n",
    "       cnts = [[0] * 26 for _ in range(n)]\n",
    "       for w in words:\n",
    "          for i, c in enumerate(w):\n",
    "             cnts[i][ord(c) - ord('a')] += 1\n",
    "       return dfs(0, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, words: List[str], target: str) -> int:\n",
    "       MOD = 10 ** 9 + 7\n",
    "       @cache\n",
    "       def dfs(i: int, j: int) -> int:\n",
    "          if i == len(target):\n",
    "             return 1\n",
    "          if j == n:\n",
    "             return 0\n",
    "          res = dfs(i, j + 1) + cnts[j][ord(target[i]) - ord('a')] * dfs(i + 1, j + 1)\n",
    "          res %= MOD\n",
    "          return res\n",
    "         #  if cnts[j][ord(target[i]) - ord('0')] > 0:\n",
    "         #     res += cnts[j][ord(target[i]) - ord('0')] * dfs(i + 1, j + 1)\n",
    "          \n",
    "       n = len(words[0])\n",
    "       if len(target) > n:\n",
    "          return 0\n",
    "       cnts = [[0] * 26 for _ in range(n)]\n",
    "       for w in words:\n",
    "          for i, c in enumerate(w):\n",
    "             cnts[i][ord(c) - ord('a')] += 1\n",
    "       return dfs(0, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, words: List[str], target: str) -> int:\n",
    "        MOD = 10**9+7\n",
    "        lw, ls = len(words), len(words[0])\n",
    "        lt = len(target)\n",
    "        dic = [[0]*26 for _ in range(ls)]\n",
    "\n",
    "        for i in range(ls):\n",
    "            for j in range(lw):\n",
    "                dic[i][(ord(words[j][i]) & 31) - 1] += 1\n",
    "\n",
    "        @cache\n",
    "        def fun(nows, nowt):\n",
    "            if nowt == lt:\n",
    "                return 1\n",
    "            if nows == ls:\n",
    "                return 0\n",
    "            return dic[nows][(ord(target[nowt]) & 31) - 1]*fun(nows+1, nowt+1) + fun(nows+1, nowt)\n",
    "        \n",
    "        return fun(0, 0) % MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, words: List[str], target: str) -> int:\n",
    "        MOD = 10**9 + 7\n",
    "\n",
    "        n = len(words[0])\n",
    "        m = len(words)\n",
    "        dic_lst = [Counter([words[i][k] for i in range(m)]) for k in range(n)]\n",
    "        t = len(target)\n",
    "        dp = [[0] * t for i in range(n)]\n",
    "        cur = 0\n",
    "        \n",
    "        for i in range(n):\n",
    "            if target[0] in dic_lst[i]:\n",
    "                cur += dic_lst[i][target[0]]\n",
    "            dp[i][0] = cur\n",
    "        \n",
    "        for i in range(1, n):\n",
    "            for k in range(1, t):\n",
    "                if target[k] in dic_lst[i]:\n",
    "                    dp[i][k] = dic_lst[i][target[k]] * dp[i-1][k-1] + dp[i-1][k]\n",
    "                else:\n",
    "                    dp[i][k] = dp[i-1][k]\n",
    "        \n",
    "        return dp[-1][-1] % (10**9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, words: List[str], target: str) -> int:\n",
    "        MOD = 10**9+7\n",
    "        lw, ls = len(words), len(words[0])\n",
    "        lt = len(target)\n",
    "        dic = [[0]*26 for _ in range(ls)]\n",
    "\n",
    "        for i in range(ls):\n",
    "            for j in range(lw):\n",
    "                dic[i][(ord(words[j][i]) & 31) - 1] += 1\n",
    "        \n",
    "        dp = [[0]*lt + [1] for _ in range(ls+1)]\n",
    "        for nowt in range(lt-1, -1, -1):\n",
    "            for nows in range(ls-1, -1, -1):\n",
    "                dp[nows][nowt] = dic[nows][(ord(target[nowt]) & 31) - 1]*dp[nows+1][nowt+1] + dp[nows+1][nowt]\n",
    "        return dp[0][0] % MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, words: List[str], target: str) -> int:\n",
    "        m, n = len(target), len(words[0])\n",
    "        word_chars = []\n",
    "        for i in range(n):\n",
    "            word_chars.append(collections.Counter(word[i] for word in words))\n",
    "        \n",
    "        # dp[i][j] = # of ways to form target[:i] using words[:j]\n",
    "        dp = [[0] * (n+1) for _ in range(m+1)]\n",
    "        for i in range(n+1): dp[0][i] = 1\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                dp[i+1][j+1] = word_chars[j][target[i]] * dp[i][j] + dp[i+1][j]\n",
    "\n",
    "        return dp[-1][-1] % (10 ** 9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, words: List[str], target: str) -> int:\n",
    "        m, n, t = len(words), len(words[0]), len(target)\n",
    "        d = [Counter([x[k] for x in words]) for k in range(n)]\n",
    "        dp = [[0] * t for _ in range(n)]\n",
    "        cur = 0\n",
    "        for i in range(n):\n",
    "            x = target[0] \n",
    "            if x in d[i]:\n",
    "                cur += d[i][x]\n",
    "            dp[i][0] = cur\n",
    "        for i in range(1, n):\n",
    "            for j in range(1, t):\n",
    "                c = target[j]\n",
    "                if c in d[i]:\n",
    "                    dp[i][j] = dp[i-1][j] + dp[i-1][j-1] * d[i][c]\n",
    "                else:\n",
    "                    dp[i][j] = dp[i-1][j]\n",
    "        return dp[-1][-1] % (10 ** 9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, words: List[str], target: str) -> int:\n",
    "        n = len(words[0])\n",
    "        m = len(target)\n",
    "        l = len(words)\n",
    "        dp = [[0 for _ in range(m)] for __ in range(n)]\n",
    "        coef=[Counter([words[i][k] for i in range(l)]) for k in range(n)]\n",
    "        cur = 0\n",
    "        for i in range(n):\n",
    "            cur_s = target[0]\n",
    "            if cur_s in coef[i]:\n",
    "                cur += coef[i][cur_s]\n",
    "            dp[i][0] = cur\n",
    "        for t in range(1,m):\n",
    "            cur_s = target[t]\n",
    "            for i in range(1,n):\n",
    "                if cur_s in coef[i]:\n",
    "                    dp[i][t] = coef[i][cur_s]*dp[i-1][t-1] + dp[i-1][t]\n",
    "                \n",
    "                else:\n",
    "                    dp[i][t] = dp[i-1][t]\n",
    "        \n",
    "        return int(dp[-1][-1] % (10**9 + 7))\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, words: List[str], target: str) -> int:\n",
    "        mod = 10**9 + 7\n",
    "        n1 = len(words[0])\n",
    "        cnt = []\n",
    "        for i in range(n1):\n",
    "            dict_tmp = {}\n",
    "            for k in range(26):\n",
    "                dict_tmp[chr(97+k)] = 0\n",
    "            for j in range(len(words)):\n",
    "                dict_tmp[words[j][i]] += 1\n",
    "                    # dict_tmp[words[j][i]] % mod\n",
    "            cnt.append(dict_tmp)\n",
    "        # print(words)\n",
    "        # print(target)\n",
    "        # print(cnt)\n",
    "        dp = [[0 for _ in range(len(target)+1)] for _ in range(n1+1)]\n",
    "\n",
    "        # dp[i][j]: 第i位词典字符起，target从第j个开始到最后, i, j 从第0个开始计数\n",
    "        # dp[i][j] = dp[i+1]dp[j] + dp[i+1]dp[j+1] * cnt[i-1][target[j-1]]\n",
    "        dp[n1-1][len(target)-1] = cnt[n1 - 1][target[-1]]\n",
    "        # print(dp)\n",
    "        for i in range(n1-1, -1, -1):\n",
    "            dp[i][len(target)-1] = cnt[i][target[-1]] + dp[i+1][len(target)-1]\n",
    "            # dp[i][len(target)-1] %= mod\n",
    "        # print(dp)\n",
    "        for i in range(n1-1, -1, -1):\n",
    "            # for j in range(1, len(target)+1):\n",
    "            for j in range(len(target)-2, -1, -1):\n",
    "                dp[i][j] = dp[i+1][j] + dp[i+1][j+1] * cnt[i][target[j]]\n",
    "                # dp[i][j] %= mod\n",
    "        # print(dp)\n",
    "        return dp[0][0] % mod\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "mod = 1000000007\n",
    "class Solution:\n",
    "    def numWays(self, words: List[str], target: str) -> int:\n",
    "        d = defaultdict(lambda :0)\n",
    "        for w in words:\n",
    "            for i,x in enumerate(w):\n",
    "                d[(i,x)]+=1\n",
    "        \n",
    "        n = len(words[0])\n",
    "        m = len(target)\n",
    "        @cache \n",
    "        def f(x,y):\n",
    "            if x >= n:\n",
    "                return 0\n",
    "            if y == m-1:\n",
    "                return (d[(x,target[y])] + f(x+1, y)) % mod\n",
    "            return (d[(x,target[y])] * f(x+1,y+1) + f(x+1,y)) % mod\n",
    "            \n",
    "        return f(0,0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, s: str) -> int:\n",
    "        o = sum(1 for c in s if c == '1')\n",
    "        if o % 3:\n",
    "            return 0\n",
    "        mod = 1000000007\n",
    "        n = len(s)\n",
    "        o //= 3\n",
    "        if o == 0:\n",
    "            return ((n - 2) * (n - 1)) // 2 % mod\n",
    "        l, r = 0, n - 1\n",
    "        sl, sr = 0, 0\n",
    "        while sl < o:\n",
    "            sl += int(s[l])\n",
    "            l += 1\n",
    "        while sr < o:\n",
    "            sr += int(s[r])\n",
    "            r -= 1\n",
    "        p1, p2 = 1, 1\n",
    "        while s[l] == '0':\n",
    "            p1 += 1\n",
    "            l += 1\n",
    "        while s[r] == '0':\n",
    "            p2 += 1\n",
    "            r -= 1\n",
    "        return (p1 * p2) % mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, s: str) -> int:\n",
    "        MOD = 10**9 + 7\n",
    "        \n",
    "        # 计算 '1' 的总数\n",
    "        ones_count = s.count('1')\n",
    "        \n",
    "        # 如果 '1' 的总数不能被3整除，无法分割成三个部分\n",
    "        if ones_count % 3 != 0:\n",
    "            return 0\n",
    "        \n",
    "        # 如果没有 '1'，可以选择分割点的方式为 C(n-2, 2) 种\n",
    "        if ones_count == 0:\n",
    "            n = len(s)\n",
    "            return ((n - 2) * (n - 1) // 2) % MOD\n",
    "        \n",
    "        # 计算每个部分 '1' 的数量\n",
    "        ones_per_part = ones_count // 3\n",
    "        \n",
    "        # 初始化变量\n",
    "        first_cut, second_cut = 0, 0\n",
    "        \n",
    "        # 找到第一个分割点\n",
    "        count = 0\n",
    "        for i in range(len(s)):\n",
    "            if s[i] == '1':\n",
    "                count += 1\n",
    "            if count == ones_per_part:\n",
    "                first_cut = i\n",
    "                break\n",
    "        \n",
    "        # 找到第二个分割点\n",
    "        count = 0\n",
    "        for i in range(first_cut + 1, len(s)):\n",
    "            if s[i] == '1':\n",
    "                count += 1\n",
    "            if count == ones_per_part:\n",
    "                second_cut = i\n",
    "                break\n",
    "        \n",
    "        # 计算两侧零的个数\n",
    "        zero_count_left = 0\n",
    "        zero_count_mid = 0\n",
    "        \n",
    "        for i in range(first_cut + 1,len(s)):\n",
    "            if s[i] == '0':\n",
    "                zero_count_mid += 1\n",
    "            else:\n",
    "                break\n",
    "        \n",
    "        count = 0\n",
    "        for i in range(second_cut + 1, len(s)):\n",
    "            if s[i] == '1':\n",
    "                break\n",
    "            count += 1\n",
    "        \n",
    "        zero_count_right = count\n",
    "        \n",
    "        return ((zero_count_mid + 1) * (zero_count_right + 1)) % MOD\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, s: str) -> int:\n",
    "        cnt = s.count('1')\n",
    "        # 不是3的倍数，不可能分割\n",
    "        if cnt % 3:    \n",
    "            return 0\n",
    "        # 只有0，相当于从长度-1中选2个切割点\n",
    "        if cnt == 0:\n",
    "            return comb(len(s) - 1, 2) % (10 ** 9 + 7)\n",
    "        \n",
    "        part1 = cnt // 3\n",
    "        part2 = part1 << 1\n",
    "        cnt1 = cnt2 = 1\n",
    "        cnt = 0\n",
    "        for c in s:\n",
    "            if c == '1':\n",
    "                cnt += 1\n",
    "            elif cnt == part1:\n",
    "                cnt1 += 1\n",
    "            elif cnt == part2:\n",
    "                cnt2 += 1\n",
    "        \n",
    "        \n",
    "        return cnt1 * cnt2 % (10 ** 9 + 7)\n",
    "\n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, s: str) -> int:\n",
    "        num = 0\n",
    "        n = len(s)\n",
    "        for i in range(n):\n",
    "            if s[i] == '1':\n",
    "                num += 1\n",
    "        if num == 0:\n",
    "            return ((n-2)*(n-1)//2)%1000000007\n",
    "        if num%3 != 0:\n",
    "            return 0\n",
    "        tmp = num//3\n",
    "        i1,i2,i3,i4 = 0,0,0,0\n",
    "        count_1 = 0\n",
    "        for i in range(n):\n",
    "            if s[i] == '1':\n",
    "                count_1 += 1\n",
    "                if count_1 == tmp:\n",
    "                    i1 = i\n",
    "                if count_1 == (tmp + 1):\n",
    "                    i2 = i\n",
    "                if count_1 == (tmp*2):\n",
    "                    i3 = i\n",
    "                if count_1 == (tmp*2+1):\n",
    "                    i4 = i\n",
    "        return ((i2-i1)*(i4-i3))%1000000007"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "M = 10**9+7\n",
    "class Solution:\n",
    "    def numWays(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        ones = 0\n",
    "        for c in s:\n",
    "            if(c == '1'):\n",
    "                ones += 1\n",
    "        if(ones % 3 != 0):\n",
    "            return 0\n",
    "        if(ones == 0):\n",
    "            return (n-1)*(n-2)//2 % M\n",
    "        ones_cnt = ones // 3\n",
    "        pos = [[-1,-1],[-1,-1],[-1,-1]]\n",
    "        pi = 0\n",
    "        tmp = 0\n",
    "        for i in range(len(s)):\n",
    "            if(s[i] == '1'):\n",
    "                if(tmp == 0):\n",
    "                    pos[pi][0] = i\n",
    "                tmp += 1\n",
    "            if(tmp == ones_cnt):\n",
    "                pos[pi][1] = i \n",
    "                tmp = 0\n",
    "                pi += 1\n",
    "        result = (pos[1][0] - pos[0][1])*(pos[2][0]-pos[1][1])\n",
    "        return result % M"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, s: str) -> int:\n",
    "        n = s.count(\"1\")\n",
    "        if n%3!=0:\n",
    "            return 0\n",
    "        if n==0:\n",
    "            return comb(len(s)-1,2)%(10**9+7)\n",
    "        x = n//3\n",
    "        t = 0\n",
    "        a = -2\n",
    "        ans = []\n",
    "        while a!=-1:\n",
    "            a = -1 if a==-2 else a\n",
    "            a = s.find(\"1\",a+1)\n",
    "            if t==x-1:\n",
    "                ans.append(a)\n",
    "            if t==x:\n",
    "                ans.append(a)\n",
    "            if t==x*2-1:\n",
    "                ans.append(a)\n",
    "            if t==x*2:\n",
    "                ans.append(a)\n",
    "            t += 1\n",
    "        return ((ans[1]-ans[0])*(ans[3]-ans[2])) %(10**9+7)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, s: str) -> int:\n",
    "        n,m=len(s),s.count('1')\n",
    "        if(m%3!=0):return 0\n",
    "        if(m==0):return (n-1)*(n-2)//2%1000000007\n",
    "        m/=3;x,y,z=0,0,0\n",
    "        for i in range(n):\n",
    "            if(s[i]=='1'):\n",
    "                z+=1\n",
    "                if(z==m):x=i;break\n",
    "        for i in range(x+1,n):\n",
    "            if(s[i]=='1'):x,y,z=i-x,i,0;break\n",
    "        for i in range(y,n):\n",
    "            if(s[i]=='1'):\n",
    "                z+=1\n",
    "                if(z==m):y=i;break\n",
    "        for i in range(y+1,n):\n",
    "            if(s[i]=='1'):y=i-y;break\n",
    "        return x*y%1000000007"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import Counter\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, s: str) -> int:\n",
    "        all = Counter(s)['1']\n",
    "        if all%3 != 0:\n",
    "            return 0\n",
    "        standard = all//3\n",
    "        length = len(s)\n",
    "        if all == 0:\n",
    "            return int((length-1)*(length-2)/2) % 1000000007\n",
    "        start_index = 0\n",
    "        end_index = 0\n",
    "        index = -1\n",
    "        count = 0\n",
    "        while -index<length:\n",
    "            if s[index] == '1':\n",
    "                count += 1\n",
    "                if count == standard:\n",
    "                    end_index = index\n",
    "                if count > standard:\n",
    "                    start_index = index\n",
    "                    break\n",
    "            index -= 1\n",
    "        ans = end_index-start_index\n",
    "        start_index = end_index = index = count = 0\n",
    "        while index<length:\n",
    "            if s[index] == '1':\n",
    "                count += 1\n",
    "                if count == standard:\n",
    "                    start_index = index\n",
    "                if count > standard:\n",
    "                    end_index = index\n",
    "                    break\n",
    "            index += 1\n",
    "        ans *= (end_index-start_index)\n",
    "        return ans % 1000000007"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, s: str) -> int:\n",
    "        #只分成3个字符串\n",
    "        #s中的1 平均分配给s1,s2,s3\n",
    "\n",
    "        #先统计一共有几个1\n",
    "        l = len(s)\n",
    "        sum_1 = 0\n",
    "        for i in s:\n",
    "            if i == '1':\n",
    "                sum_1 += 1\n",
    "        print('s中一共有%d个1'%sum_1)\n",
    "\n",
    "        if sum_1%3 != 0:\n",
    "            return 0\n",
    "        elif sum_1 == 0:\n",
    "            res = 0\n",
    "            for i in range(l-2):\n",
    "                res += l - 2 - i\n",
    "            return res%(10**9+7)\n",
    "        else:\n",
    "            n = sum_1//3 #每个子字符串中'1'的数量\n",
    "        \n",
    "        #由于s1 + s2 + s3 = s 所以'1'的分配是有顺序的 \n",
    "        #前n个1给s1，中间n个1给s2，最好n个1给s3 (假设n>0)\n",
    "\n",
    "        #观察s1,s2,s3交互的边界\n",
    "        Dict = {n:0,n+1:0,2*n:0,2*n+1:0}\n",
    "        count = 0\n",
    "        index = 0\n",
    "        #print([n,n+1,2*n,2*n+1])\n",
    "        for i in s:\n",
    "            if i=='1':\n",
    "                count += 1\n",
    "                #print(count)\n",
    "                if count in Dict:\n",
    "                    Dict[count] = index\n",
    "            index += 1\n",
    "        print(Dict)\n",
    "        #print(49001**2)\n",
    "        return (Dict[n+1]-Dict[n])*(Dict[2*n+1]-Dict[2*n])%(10**9+7)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, s: str) -> int:\n",
    "        count_1 = s.count('1')\n",
    "        mod = 10 ** 9 + 7\n",
    "        n = len(s)\n",
    "        if count_1 % 3 != 0:\n",
    "            return 0\n",
    "        if count_1 == 0:\n",
    "            return (n - 2) * (n - 1) // 2 % mod\n",
    "        gap1 = 0\n",
    "        gap2 = 0\n",
    "        total_1 = 0\n",
    "        # gap is the count for zeros between two chunks of ones\n",
    "        for c in s:\n",
    "            if c == '1':\n",
    "                total_1 += 1\n",
    "            if c == '0':\n",
    "                if total_1 == count_1 // 3:\n",
    "                    gap1 += 1\n",
    "                if total_1 == count_1 // 3 * 2:\n",
    "                    gap2 += 1\n",
    "        return (gap1 + 1) * (gap2 + 1) % mod                \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "M = 10**9+7\n",
    "class Solution:\n",
    "    def numWays(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        ones = 0\n",
    "        for c in s:\n",
    "            if(c == '1'):\n",
    "                ones += 1\n",
    "        if(ones % 3 != 0):\n",
    "            return 0\n",
    "        if(ones == 0):\n",
    "            return (n-1)*(n-2)//2 % M\n",
    "        ones_cnt = ones // 3\n",
    "        pos = [[-1,-1],[-1,-1],[-1,-1]]\n",
    "        pi = 0\n",
    "        tmp = 0\n",
    "        for i in range(len(s)):\n",
    "            if(s[i] == '1'):\n",
    "                if(tmp == 0):\n",
    "                    pos[pi][0] = i\n",
    "                tmp += 1\n",
    "            if(tmp == ones_cnt):\n",
    "                pos[pi][1] = i \n",
    "                tmp = 0\n",
    "                pi += 1\n",
    "        result = (pos[1][0] - pos[0][1])*(pos[2][0]-pos[1][1])\n",
    "        return result % M"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def numWays(self, s: str) -> int:\r\n",
    "        #统计1的个数\r\n",
    "        #如果1的个数不能被3整除，直接返回0\r\n",
    "        cnt = s.count('1')\r\n",
    "        if cnt % 3 != 0:\r\n",
    "            return 0\r\n",
    "        #如果1的个数为0，那么返回C(n-2, 2)\r\n",
    "        MOD = 10 ** 9 + 7\r\n",
    "        n = len(s)\r\n",
    "        if cnt == 0:\r\n",
    "            return (n - 2) * (n - 1) // 2 % MOD\r\n",
    "        #如果1的个数能被3整除\r\n",
    "        #查找第一段和第二段的1中间有多少个0,n1\r\n",
    "        #查找第二段和第三段的1中间有多少个0,n2\r\n",
    "        #返回n1 * n2 % MOD\r\n",
    "        n1,n2 = 0,0\r\n",
    "        cnt1,cnt2 = 0,0\r\n",
    "        for i in range(n):\r\n",
    "            if s[i] == '1':\r\n",
    "                cnt1 += 1\r\n",
    "            if cnt // 3 <= cnt1 <= cnt // 3 * + 1:\r\n",
    "                n1 += 1\r\n",
    "        for i in range(n-1,-1,-1):\r\n",
    "            if s[i] == '1':\r\n",
    "                cnt2 += 1\r\n",
    "            if cnt // 3 <= cnt2 <= cnt // 3 * + 1:\r\n",
    "                n2 += 1\r\n",
    "        return n1 * n2 % MOD\r\n",
    "     "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, s: str) -> int:\n",
    "        x, cnt, f1, f2 = s.count('1'), 0, 0, 0\n",
    "        if x%3: return 0\n",
    "        if x==0: return ((len(s)-1)*(len(s)-2)//2)%1000000007\n",
    "        for i in range(len(s)):\n",
    "            if s[i]=='1': cnt += 1\n",
    "            if not f1 and cnt==x//3: f1 = len(s)-i-len(s[i+1:].lstrip('0'))\n",
    "            if cnt==2*x//3: \n",
    "                f2 = len(s)-i-len(s[i+1:].lstrip('0'))\n",
    "                return f1*f2%1000000007"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, s: str) -> int:\n",
    "        mod = int(1e9 + 7)\n",
    "\n",
    "\n",
    "        sum_ = 0\n",
    "\n",
    "        for ss in s:\n",
    "            if ss == '1':\n",
    "                sum_ += 1\n",
    "        \n",
    "        if sum_ % 3 != 0:\n",
    "            return 0\n",
    "\n",
    "        \n",
    "        cnt = sum_ // 3\n",
    "\n",
    "        if cnt == 0:\n",
    "            return ((len(s) - 1) * (len(s) - 2) // 2) % mod\n",
    "\n",
    "        \n",
    "        presum = 0\n",
    "        for i in range(len(s)):\n",
    "            if s[i] == '1':\n",
    "                presum += 1\n",
    "                if presum == cnt:\n",
    "                    break\n",
    "        \n",
    "        leftStart = i\n",
    "        i += 1\n",
    "        while i < len(s) and s[i] == '0':\n",
    "            i += 1\n",
    "        \n",
    "        leftEnd = i - 1\n",
    "\n",
    "\n",
    "\n",
    "        suffix = 0\n",
    "        for i in range(len(s) - 1, -1, -1):\n",
    "            if s[i] == '1':\n",
    "                suffix += 1\n",
    "                if suffix == cnt:\n",
    "                    break\n",
    "        \n",
    "        rightEnd = i \n",
    "        i -= 1\n",
    "\n",
    "        while i >= 0 and s[i] == '0':\n",
    "            i -= 1\n",
    "\n",
    "        rightStart = i + 1\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        return (leftEnd - leftStart + 1) * (rightEnd - rightStart + 1) % mod\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        mod = 10 ** 9 + 7\n",
    "        ones = s.count('1')\n",
    "        if ones % 3:\n",
    "            return 0\n",
    "        if ones == 0:\n",
    "            return comb(n - 1, 2) % mod \n",
    "        per = ones // 3\n",
    "        rec = []\n",
    "        cnt = 0\n",
    "        for i, j in enumerate(s):\n",
    "            if j == '1':\n",
    "                cnt += 1\n",
    "                for k in [per, per + 1, 2 * per, 2 * per + 1]:\n",
    "                    if k == cnt:\n",
    "                        rec.append(i)\n",
    "        ans = (rec[1] - rec[0]) * (rec[3] - rec[2]) % mod \n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, s: str) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "        \n",
    "        cnt = s.count('1')\n",
    "        if cnt % 3:\n",
    "            return 0\n",
    "\n",
    "        if cnt == 0:\n",
    "            n = len(s)\n",
    "            if n < 3:\n",
    "                return 0\n",
    "            \n",
    "            return (n-1) * (n-2) // 2 % MOD\n",
    "\n",
    "\n",
    "        \n",
    "        cnt //= 3\n",
    "        cnt1 = 0\n",
    "        cntPre = 1\n",
    "        cntAfter = 1\n",
    "\n",
    "        for c in s:\n",
    "            if c == '1':\n",
    "                cnt1 += 1\n",
    "            \n",
    "            if cnt1 == cnt and c == '0':\n",
    "                cntPre += 1\n",
    "            elif cnt1 == cnt * 2 and c == '0':\n",
    "                cntAfter += 1\n",
    "\n",
    "        return cntPre * cntAfter % MOD\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def numWays(self, s: str) -> int:\r\n",
    "        #统计1的个数\r\n",
    "        #如果1的个数不能被3整除，直接返回0\r\n",
    "        cnt = s.count('1')\r\n",
    "        if cnt % 3 != 0:\r\n",
    "            return 0\r\n",
    "        #如果1的个数为0，那么返回C(n-2, 2)\r\n",
    "        MOD = 10 ** 9 + 7\r\n",
    "        n = len(s)\r\n",
    "        if cnt == 0:\r\n",
    "            return (n - 2) * (n - 1) // 2 % MOD\r\n",
    "        #如果1的个数能被3整除\r\n",
    "        #查找第一段和第二段的1中间有多少个0,n1\r\n",
    "        #查找第二段和第三段的1中间有多少个0,n2\r\n",
    "        #返回n1 * n2 % MOD , n1n2已经加1\r\n",
    "        n1,n2 = 0,0\r\n",
    "        cnt1,cnt2 = 0,0\r\n",
    "        for i in range(n):\r\n",
    "            if s[i] == '1':\r\n",
    "                cnt1 += 1\r\n",
    "            if cnt // 3 <= cnt1 <= cnt // 3 * + 1:\r\n",
    "                n1 += 1\r\n",
    "        for i in range(n-1,-1,-1):\r\n",
    "            if s[i] == '1':\r\n",
    "                cnt2 += 1\r\n",
    "            if cnt // 3 <= cnt2 <= cnt // 3 * + 1:\r\n",
    "                n2 += 1\r\n",
    "        return n1 * n2 % MOD\r\n",
    "     "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "M = 10**9+7\n",
    "class Solution:\n",
    "    def numWays(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        ones = 0\n",
    "        for c in s:\n",
    "            if(c == '1'):\n",
    "                ones += 1\n",
    "        if(ones % 3 != 0):\n",
    "            return 0\n",
    "        if(ones == 0):\n",
    "            return (n-1)*(n-2)//2 % M\n",
    "        ones_cnt = ones // 3\n",
    "        pos = [[-1,-1],[-1,-1],[-1,-1]]\n",
    "        pi = 0\n",
    "        tmp = 0\n",
    "        for i in range(len(s)):\n",
    "            if(s[i] == '1'):\n",
    "                if(tmp == 0):\n",
    "                    pos[pi][0] = i\n",
    "                tmp += 1\n",
    "            if(tmp == ones_cnt):\n",
    "                pos[pi][1] = i \n",
    "                tmp = 0\n",
    "                pi += 1\n",
    "        result = (pos[1][0] - pos[0][1])*(pos[2][0]-pos[1][1])\n",
    "        return result % M"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, s: str) -> int:\n",
    "        MOD = 10**9+7\n",
    "        n = len(s)\n",
    "        c = s.count('1')\n",
    "        if c % 3 != 0: return 0\n",
    "        a = c // 3\n",
    "        if a == 0:\n",
    "            return ((n - 2) * (n - 1) // 2) % MOD\n",
    "        i1, i2, i3, i4 = 0, 0, 0, 0\n",
    "        cnt = 0\n",
    "        for i, c in enumerate(s):\n",
    "            if c == '1':\n",
    "                cnt += 1\n",
    "                print(i, cnt)\n",
    "                if cnt == a:\n",
    "                    i1 = i\n",
    "                if cnt == a + 1:\n",
    "                    i2 = i\n",
    "                if cnt == 2 * a:\n",
    "                    i3 = i\n",
    "                if cnt == 2 * a + 1:\n",
    "                    i4 = i\n",
    "        # print(i1, i2, i3, i4)\n",
    "        return (i2 - i1) * (i4 - i3) % MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def numWays(self, s: str) -> int:\r\n",
    "        o = sum(1 for c in s if c == '1')\r\n",
    "        if o % 3:\r\n",
    "            return 0\r\n",
    "        mod = 1000000007\r\n",
    "        n = len(s)\r\n",
    "        o //= 3\r\n",
    "        if o == 0:\r\n",
    "            return ((n - 2) * (n - 1)) // 2 % mod\r\n",
    "        l, r = 0, n - 1\r\n",
    "        sl, sr = 0, 0\r\n",
    "        while sl < o:\r\n",
    "            sl += int(s[l])\r\n",
    "            l += 1\r\n",
    "        while sr < o:\r\n",
    "            sr += int(s[r])\r\n",
    "            r -= 1\r\n",
    "        p1, p2 = 1, 1\r\n",
    "        while s[l] == '0':\r\n",
    "            p1 += 1\r\n",
    "            l += 1\r\n",
    "        while s[r] == '0':\r\n",
    "            p2 += 1\r\n",
    "            r -= 1\r\n",
    "        return (p1 * p2) % mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOD = 10 ** 9 + 7\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, s: str) -> int:\n",
    "        cnt = s.count('1')\n",
    "        if cnt % 3: return 0\n",
    "        if cnt == 0:\n",
    "            return comb(len(s) - 1, 2) % MOD\n",
    "        t = cnt // 3\n",
    "        p = [i for i, x in enumerate(s) if x == '1']\n",
    "        t2 = cnt // 3 * 2\n",
    "        cnt1 = p[t] - p[t - 1]\n",
    "        cnt2 = p[t2] - p[t2 - 1]\n",
    "        return (cnt1 * cnt2) % MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, s: str) -> int:\n",
    "        news = [i for i,num in enumerate(s) if num=='1']\n",
    "        k = len(news)\n",
    "        if k%3:return 0\n",
    "        if not k:return (len(s)-1)*(len(s)-2)//2%(10**9+7)        \n",
    "        return (news[k//3]-news[k//3-1])*(news[k//3*2]-news[k//3*2-1])%(10**9+7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, s: str) -> int:\n",
    "        # 1的数量必平分，然后统计间隔的0的数量相乘\n",
    "        # 如果全是0的话就看成组合问题\n",
    "        n = len(s)\n",
    "        one_indexs = [k for k,v in enumerate(s) if v=='1']\n",
    "        one_count = len(one_indexs)\n",
    "        if one_count%3!=0 :\n",
    "            return 0\n",
    "        if one_count == 0:\n",
    "            return int((n-1)*(n-2)/2)%(1000000007)\n",
    "        one_need = int(one_count/3) \n",
    "        return ((one_indexs[one_need] - one_indexs[one_need-1]) * (one_indexs[one_need*2] - one_indexs[one_need*2-1]))%1000000007\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, s: str) -> int:\n",
    "        MODULO = 1000000007\n",
    "\n",
    "        ones = list()\n",
    "        n = len(s)\n",
    "        for i, digit in enumerate(s):\n",
    "            if digit == \"1\":\n",
    "                ones.append(i)\n",
    "        \n",
    "        m = len(ones)\n",
    "        if m % 3 != 0:\n",
    "            return 0\n",
    "        \n",
    "        if m == 0:\n",
    "            ways = (n - 1) * (n - 2) // 2\n",
    "            return ways % MODULO\n",
    "        else:\n",
    "            index1, index2 = m // 3, m // 3 * 2;\n",
    "            count1 = ones[index1] - ones[index1 - 1]\n",
    "            count2 = ones[index2] - ones[index2 - 1]\n",
    "            ways = count1 * count2\n",
    "            return ways % MODULO\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, s: str) -> int:\n",
    "        cnt = [i for i,n in enumerate(s) if n == '1']\n",
    "        # for i in range(len(s)):\n",
    "        #     if s[i] == '1':\n",
    "        #         cnt.append(i)\n",
    "        if len(cnt) % 3 != 0:return 0\n",
    "        if len(cnt) == 0:return int(((len(s)-1)*(len(s)-2)//2)%(1000000007))\n",
    "        gap = int(len(cnt) / 3)\n",
    "        return int(((cnt[gap]-cnt[gap-1])*(cnt[gap*2]-cnt[gap*2-1]))%(1000000007))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, s: str) -> int:\n",
    "        news = [i for i,num in enumerate(s) if num=='1']\n",
    "        k = len(news)\n",
    "        if k%3:return 0\n",
    "        if not k:return (len(s)-1)*(len(s)-2)//2%1000000007        \n",
    "        return (news[k//3]-news[k//3-1])*(news[k//3*2]-news[k//3*2-1])%(10**9+7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, s: str) -> int:\n",
    "        news = [i for i,num in enumerate(s) if num=='1']\n",
    "        k = len(news)\n",
    "        if k%3:return 0\n",
    "        if not k:return (len(s)-1)*(len(s)-2)//2%1000000007        \n",
    "        return (news[k//3]-news[k//3-1])*(news[k//3*2]-news[k//3*2-1])%1000000007\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, s: str) -> int:\n",
    "        ones = list()\n",
    "        for i, c in enumerate(s):\n",
    "            if c == \"1\":\n",
    "                ones.append(i)\n",
    "        m = len(ones)\n",
    "        if m % 3 != 0:\n",
    "            return 0\n",
    "        if m == 0:\n",
    "            return ((len(s)-1)*(len(s)-2)//2) % (10**9+7)\n",
    "        else:\n",
    "            index1 = m // 3\n",
    "            index2 = 2 * m // 3\n",
    "            num1 = ones[index1] - ones[index1-1]\n",
    "            num2 = ones[index2] - ones[index2-1]\n",
    "            return (num1 * num2) % (10**9+7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, s: str) -> int:\n",
    "        mod = 10**9 + 7\n",
    "        n = len(s)\n",
    "        ones = [i for i, num in enumerate(s) if num == \"1\"] \n",
    "        k = len(ones)\n",
    "        if k == 0:\n",
    "            return (n-1)*(n-2)//2%mod \n",
    "\n",
    "        a,b = divmod(k,3)\n",
    "        if b:\n",
    "            return 0\n",
    "\n",
    "        return (ones[a]-ones[a-1])*(ones[a*2]-ones[a*2-1])%mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, s: str) -> int:\n",
    "        oneIndex = [i for i,num in enumerate(s) if num=='1']\n",
    "        k = len(oneIndex)\n",
    "        if k%3:\n",
    "            return 0\n",
    "\n",
    "        n = len(s)\n",
    "        if k==0:\n",
    "            res = (n-1)*(n-2) // 2\n",
    "            return res%1000000007\n",
    "\n",
    "        index1 = k//3\n",
    "        index2 = k//3 * 2\n",
    "        count1 = oneIndex[index1]-oneIndex[index1-1]\n",
    "        count2 = oneIndex[index2]-oneIndex[index2-1]\n",
    "        return count1 * count2 % 1000000007        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, s: str) -> int:\n",
    "        length = len(s)\n",
    "        total_1 = 0\n",
    "        list_1 = []\n",
    "        for i in range(length):\n",
    "            if int(s[i]) == 1:\n",
    "                total_1 += 1\n",
    "                list_1.append(i)\n",
    "\n",
    "        if total_1 % 3 != 0:\n",
    "            return 0\n",
    "        if list_1 == []:\n",
    "            return int((math.comb(length-1,2) % (10e8+7)))\n",
    "        ans = (list_1[int(total_1 / 3 - 1)] - list_1[int(total_1 / 3)]) * (list_1[int(total_1 / 3 * 2 - 1)] - \n",
    "                                                                   list_1[int(total_1 / 3 * 2)])\n",
    "        return int(ans % (10e8+7))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, s: str) -> int:\n",
    "        slist =[]\n",
    "        for idx, st in enumerate(s):\n",
    "            if st == '1':\n",
    "                slist.append(idx)\n",
    "        n = len(slist)\n",
    "\n",
    "        BIGNUM = 1000000007\n",
    "        if n % 3 or len(s) < 3:\n",
    "            return 0\n",
    "\n",
    "        if n == 0:\n",
    "            return ((len(s)-1)*(len(s)-2)//2)%BIGNUM\n",
    "\n",
    "        if n > 0:\n",
    "            ave = len(slist)//3\n",
    "            left0 = slist[ave]-slist[ave-1]\n",
    "            right0 = slist[-ave]-slist[-ave-1]\n",
    "            return (left0*right0)%BIGNUM\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, s: str) -> int:\n",
    "        MODULO = 1000000007\n",
    "        n=len(s)\n",
    "        ones=list()\n",
    "        for i,x in enumerate(s):\n",
    "            if x==\"1\":\n",
    "                ones.append(i)\n",
    "        \n",
    "        m=len(ones)\n",
    "\n",
    "        if m%3!=0:\n",
    "            return 0\n",
    "\n",
    "        if m==0:\n",
    "            return ((n-1)*(n-2)//2)%MODULO\n",
    "        else:\n",
    "            index1=m//3\n",
    "            index2=m//3*2\n",
    "            count1=ones[index1]-ones[index1-1]\n",
    "            count2=ones[index2]-ones[index2-1]\n",
    "            ways=count1*count2\n",
    "            return ways%MODULO\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, s: str) -> int:\n",
    "        cnt = [i for i,n in enumerate(s) if n == '1']\n",
    "        # for i in range(len(s)):\n",
    "        #     if s[i] == '1':\n",
    "        #         cnt.append(i)\n",
    "        if len(cnt) % 3 != 0:return 0\n",
    "        if len(cnt) == 0:return int(((len(s)-1)*(len(s)-2)//2)%(1000000007))\n",
    "        gap = int(len(cnt) / 3)\n",
    "        return int(((cnt[gap]-cnt[gap-1])*(cnt[gap*2]-cnt[gap*2-1]))%(1000000007))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, s: str) -> int:\n",
    "        MODULO = 1000000007\n",
    "\n",
    "        ones = list()\n",
    "        n = len(s)\n",
    "        for i, digit in enumerate(s):\n",
    "            if digit == \"1\":\n",
    "                ones.append(i)\n",
    "        \n",
    "        m = len(ones)\n",
    "        if m % 3 != 0:\n",
    "            return 0\n",
    "        \n",
    "        if m == 0:\n",
    "            ways = (n - 1) * (n - 2) // 2\n",
    "            return ways % MODULO\n",
    "        else:\n",
    "            index1, index2 = m // 3, m // 3 * 2\n",
    "            count1 = ones[index1] - ones[index1 - 1]\n",
    "            count2 = ones[index2] - ones[index2 - 1]\n",
    "            ways = count1 * count2\n",
    "            return ways % MODULO\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # * 模拟\n",
    "    def numWays(self, s: str) -> int:\n",
    "        MODULO = 1000000007\n",
    "\n",
    "        ones = list()\n",
    "        n = len(s)\n",
    "        for i, digit in enumerate(s):\n",
    "            if digit == \"1\":\n",
    "                ones.append(i)\n",
    "        \n",
    "        m = len(ones)\n",
    "        if m % 3 != 0:\n",
    "            return 0\n",
    "        \n",
    "        if m == 0:\n",
    "            ways = (n - 1) * (n - 2) // 2\n",
    "            return ways % MODULO\n",
    "        else:\n",
    "            index1, index2 = m // 3, m // 3 * 2;\n",
    "            count1 = ones[index1] - ones[index1 - 1]\n",
    "            count2 = ones[index2] - ones[index2 - 1]\n",
    "            ways = count1 * count2\n",
    "            return ways % MODULO\n",
    "            \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, s: str) -> int:\n",
    "        news = [i for i,num in enumerate(s) if num=='1']\n",
    "        k = len(news)\n",
    "        if k%3:return 0\n",
    "        if not k:return (len(s)-1)*(len(s)-2)//2%1000000007        \n",
    "        return (news[k//3]-news[k//3-1])*(news[k//3*2]-news[k//3*2-1])%1000000007\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, s: str) -> int:\n",
    "        cnt = []\n",
    "        for i in range(len(s)):\n",
    "            if s[i] == '1':\n",
    "                cnt.append(i)\n",
    "        if len(cnt) % 3 != 0:return 0\n",
    "        if len(cnt) == 0:return int(((len(s)-1)*(len(s)-2)//2)%(1000000007))\n",
    "        gap = int(len(cnt) / 3)\n",
    "        return int(((cnt[gap]-cnt[gap-1])*(cnt[gap*2]-cnt[gap*2-1]))%(1000000007))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, s: str) -> int:\n",
    "        cnt=s.count('1')\n",
    "        if cnt%3!=0:\n",
    "            return 0\n",
    "        if cnt==0:\n",
    "            m=len(s)\n",
    "            return int((m-1)*(m-2)/2)%(10**9+7)\n",
    "        pos=[]\n",
    "        k=int(cnt/3)\n",
    "        i=0\n",
    "        for i in range(len(s)):\n",
    "            if s[i]=='1':\n",
    "                pos.append(i)\n",
    "        s_0=pos[k]-pos[k-1]\n",
    "        s_1=pos[2*k]-pos[2*k-1]\n",
    "        return (s_0*s_1)%(10**9+7)\n",
    "        \n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, s: str) -> int:\n",
    "        news = [i for i,num in enumerate(s) if num=='1']\n",
    "        k = len(news)\n",
    "        if k%3:return 0\n",
    "        if not k:return (len(s)-1)*(len(s)-2)//2%1000000007        \n",
    "        return (news[k//3]-news[k//3-1])*(news[k//3*2]-news[k//3*2-1])%1000000007\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, s: str) -> int:\n",
    "        cnt = Counter(s)\n",
    "        n = len(s)\n",
    "        m = cnt[\"1\"]\n",
    "        if m % 3 != 0:\n",
    "            return 0\n",
    "        if m == 0:\n",
    "            return (n - 1) * (n - 2) // 2 % (10 ** 9 + 7)\n",
    "        else:\n",
    "            count = 0\n",
    "            dic = {}\n",
    "            for i, ch in enumerate(s):\n",
    "                if ch == \"1\":\n",
    "                    count += 1\n",
    "                    dic[count] = i\n",
    "            lst = []\n",
    "            for key, value in dic.items():\n",
    "                if key == m // 3 or key == m // 3 + 1:\n",
    "                    lst.append(value)\n",
    "                if key == 2 * m // 3 or key == 2 * m // 3 + 1:\n",
    "                    lst.append(value)\n",
    "            return (lst[1] - lst[0]) * (lst[3] - lst[2]) %(10 **9 + 7)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        t = 0\n",
    "        for c in s:\n",
    "            if c == '1':\n",
    "                t += 1\n",
    "        mod = 10 ** 9 + 7\n",
    "        if t % 3:\n",
    "            return 0\n",
    "        if t == 0:\n",
    "            return math.comb(n - 1,2) % mod\n",
    "        tmp = -1\n",
    "        tp = 0\n",
    "        s = list(s)\n",
    "        for i in range(n):\n",
    "            if s[i] == '1':\n",
    "                tp += 1\n",
    "            if tp == t // 3:\n",
    "                tmp = i\n",
    "                break\n",
    "        \n",
    "        z0 = 1\n",
    "        tmp += 1\n",
    "        while tmp < n and s[tmp] == '0':\n",
    "            z0 += 1\n",
    "            \n",
    "            tmp += 1\n",
    "        tmp = -1\n",
    "        tp = 0\n",
    "        for i in range(n - 1,-1,-1):\n",
    "            if s[i] == '1':\n",
    "                tp += 1\n",
    "            if tp == t // 3:\n",
    "                tmp = i\n",
    "                break\n",
    "        z1 = 1\n",
    "        tmp -= 1\n",
    "        while tmp >= 0 and s[tmp] == '0':\n",
    "            z1 += 1\n",
    "            tmp -= 1\n",
    "        return z0 * z1 % mod\n",
    "        \n",
    "            \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, s: str) -> int:\n",
    "        c=s.count('1')\n",
    "        n=len(s)\n",
    "        if c%3 :\n",
    "            return 0\n",
    "        if c==0:\n",
    "            return ((n-1)*(n-2)//2)%(10**9+7)    \n",
    "        r=c/3\n",
    "        k=-1\n",
    "        j=0\n",
    "        s=list(s)\n",
    "        \n",
    "        cur=0\n",
    "        a=[]\n",
    "        for i in range(n):\n",
    "            if s[i]=='1':\n",
    "              if k!=-1:\n",
    "                 a.append(i-k)\n",
    "                 k=-1   \n",
    "              cur+=1\n",
    "            if cur==r:\n",
    "               k=i\n",
    "               cur=0\n",
    "                   \n",
    "        return (a[0]*a[1])%(10**9+7)"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
